#include<iostream>

const int capacity = 10; 

class MaxHeap 
{
private:
   
    
    int GetParent(int i){return (i-1)/2 ;}
    int GetLeftChild(int i){return 2 * i + 1;}
    int GetRightChild(int i){return 2 * i + 2;}

    void SiftUp( int i )  // 上浮操作
    {
        while( i > 0 && array[i] > array[GetParent(i)])
        {
            std::swap(array[i],array[GetParent(i)]);
            i = GetParent(i);
        }
    } 
    

    
    void SiftDown(int i)  // 下沉操作
    {
        int leftchild = GetLeftChild(i);
        int rightchild = GetRightChild(i);

        int Max = i;
        
        if(leftchild < size && array[leftchild] > array[i])// 判断左孩子下标是否存在 同时 左孩子是否比我大
        {
            Max  = leftchild;       //左孩子比我大，那么左孩子就是最大根
        }
        if(rightchild < size && array[rightchild] > array[Max])//判断右孩子下标是否存在 同时右孩子是否比 最大根 大
        {
            Max = rightchild;       //右孩子比最大根大，那么右孩子就是最大根
        }

        if(Max != i)
        {
            std::swap(array[i],array[Max]);
            SiftDown(Max);
        }
    }
    
    int array[capacity]; //一个数组用来装 序号
    int size;  //数组当前的元素个数



public:
    MaxHeap():size(0){};

    void Insert(int value)
    {
        array[size] = value;
        SiftUp(size);
        size++;
    }
    


    //删除根

    
    void RemoveRoot()
    {
        if(size == 0)
            return;
        array[0] = array[--size];//把最新的值变成根，然后下沉
        SiftDown(0);
    }

    void show()
    {
        for(int i = 0 ; i < size;i++)
        {
            std::cout<<array[i]<<" ";
        }
        std::cout<<std::endl;
    }



};









int main()
{
    MaxHeap h;
    for(int i=0;i<10;i++)
    {
        h.Insert(i+1);
    }

    h.show();

    h.RemoveRoot();

    h.show();
}

